package 优先队列式分支限界;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Scanner;

class Test5 {
    public void addLiveNode(PriorityQueue<HeapNode> H, bbnode E, int wt, boolean ch, int lev) {
        bbnode b = new bbnode(E, ch);
        HeapNode N = new HeapNode(b, wt, lev);
        H.add(N);
    }

    public int maxLoading(int[] w, int c, int n, boolean[] bestx) {
        PriorityQueue<HeapNode> H = new PriorityQueue(1000, new comp());
        int[] r = new int[n + 1];
        r[n] = 0;
        for (int j = n - 1; j > 0; j--) {
            r[j] = r[j + 1] + w[j + 1];
        }
        int i = 1;
        bbnode E = new bbnode(null, false);
        int Ew = 0;
        while (i != n + 1) {
            if (Ew + w[i] <= c) {
                addLiveNode(H, E, Ew + w[i] + r[i], true, i + 1);
            }
            addLiveNode(H, E, Ew + r[i], false, i + 1);
            HeapNode N;
            N = H.poll();
            i = N.level;
            E = N.ptr;
            Ew = N.uweight - r[i - 1];
        }
        //构造最优解
        for (int j = n; j > 0; j--) {
            bestx[j] = E.Lchild;
            E = E.parent;
        }
        return Ew;
    }
}

//堆结点类
class HeapNode {
    bbnode ptr;
    int uweight;
    int level;

    public HeapNode() {
    }

    public HeapNode(bbnode ptr, int uweight, int level) {
        this.ptr = ptr;
        this.uweight = uweight;
        this.level = level;
    }

    public String toString() {
        return " " + this.uweight;
    }
}

class bbnode {
    bbnode parent;
    boolean Lchild;

    public bbnode(bbnode node, boolean ch) {
        this.parent = node;
        this.Lchild = ch;
    }
}

//定义比较器类
class comp implements Comparator<HeapNode> {
    @Override
    public int compare(HeapNode o1, HeapNode o2) {
        int dif = o1.uweight - o2.uweight;
        if (dif > 0) {
            return -1;
        } else if (dif == 0) {
            return 0;
        } else {
            return 1;
        }
    }
}


public class 最大装载问题 {

    public static void main(String[] args) {
        System.out.println("请输入物品总数： ");
        Scanner sc1 = new Scanner(System.in);
        int n = sc1.nextInt();
        int[] w = new int[n + 1];
        System.out.println("请输入物品重量： ");
        Scanner sc2 = new Scanner(System.in);
        for (int i = 1; i <= n; i++) {
            w[i] = sc2.nextInt();
        }
        System.out.println("请输入箱子重量： ");

        Scanner sc3 = new Scanner(System.in);
        int c1 = sc3.nextInt();
        int c2 = sc3.nextInt();
        boolean[] bestx = new boolean[100];
        Test5 t = new Test5();
        //处理第一个箱子
        System.out.println("first： " + t.maxLoading(w, c1, n, bestx));
        System.out.print("可装载重量为： ");
        int count = 0;
        for (int i = 1; i <= n; i++) {
            if (bestx[i]) {
                count++;
                System.out.print(w[i] + " ");//输出一个可行方案
            }
        }
        System.out.println();
        //处理第二个箱子
        int m = n - count;
        int[] ww = new int[m + 1];
        int k = 1;
        for (int i = 1; i <= n; i++) {
            if (!bestx[i]) {
                ww[k] = w[i];
                k++;
                bestx[i] = false;
            }
        }
        System.out.println();
        System.out.println("second: " + t.maxLoading(ww, c2, m, bestx));
        System.out.print("可装载重量为: ");
        for (int i = 1; i <= m; i++) {
            if (bestx[i]) {
                System.out.print(ww[i] + " ");//输出一个可行方案
            }
        }
    }

}
		
